package com.cqs.leetcode.tree.DFS;

import com.cqs.leetcode.TreeNode;

import java.util.HashMap;
import java.util.Map;

public class DistributeCoinsInBinaryTree979 {

    int sum = 0;
    public int distributeCoins(TreeNode root) {
        if (root == null) return 0;
        postOrder(root);
        return sum;
    }

    /**
     * 后序递归处理
     * @param root
     * @return 将root处理成符合要求的节点后，金币的结余(正数表示转移给父节点，负数表示从父节那转移数)
     */
    private int postOrder(TreeNode root) {
        int left = root.left == null ? 0 : postOrder(root.left);
        int right = root.right == null ? 0 : postOrder(root.right);
        int tmp = root.val - 1 + left + right;
        //转移次数在孩子节点调整的时候结算了
        sum += Math.abs(tmp);
        //处理完子树后，当前节点金币的差值：正数表示可以给父节点金币，负数表示需要需要像父节点借金币
        return tmp;
    }


    /**
     * 思路:
     * 从底向上处理，处理顺序后序遍历 左孩子->右孩子->父节点
     * 先处理叶子节点，叶子节点变成1，一定是从父节点挪动来的
     * 那么孩子节点变成1的插值为child.val - 1(正数表示结余，负数表示从需要从父节点借金币),
     * a.将差值更新到父节点上parent.val + child.val-1，b.差值的绝对值就是处理一个节点需要移动的次数
     * <p>
     * 后序遍历的方式递归处理
     */
    class Solution {
        int sum = 0;
        Map<TreeNode, TreeNode> parents = new HashMap<>();

        public int distributeCoins(TreeNode root) {
            postOrder(root);
            return sum;
        }

        private void postOrder(TreeNode root) {
            if (root.left != null) {
                parents.put(root.left, root);
                postOrder(root.left);
            }
            if (root.right != null) {
                parents.put(root.right, root);
                postOrder(root.right);
            }
            if (root.val != 1) {
                int dlt = root.val - 1;
                sum += Math.abs(dlt);
                TreeNode parent = parents.get(root);
                if (parent != null) {
                    parent.val += dlt;
                }
            }
        }
    }
}
